//
//  arraySolution.hpp
//  labuladong
//
//  Created by 刘振舟 on 2023/5/19.
//

#ifndef arraySolution_hpp
#define arraySolution_hpp

#include <vector>
#include <queue>
#include <string>

using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums);
    
    int removeElement(vector<int>& nums, int val);
    
    void moveZeroes(vector<int>& nums);

    vector<int> twoSum(vector<int>& numbers, int target);
    
    void reverseString(vector<char>& s);
    
    string longestPalindrome(string s);
    
    void differenceIncrease(vector<int> &diff, int first, int last, int seats) {
        diff[first - 1] += seats;
        if (last < diff.size()) {
            diff[last] -= seats;
        }
    }
    
    vector<int> differenceResult(vector<int> &diff) {
        vector<int> result(diff.size(), diff[0]);
        for (int i = 1; i < diff.size(); ++i) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
    
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (vector<int> &booking : bookings) {
            differenceIncrease(diff, booking[0], booking[1], booking[2]);
        }
        return differenceResult(diff);
    }
    
    void carDifferenceIncrease(vector<int> &diff, int first, int last, int seats) {
        diff[first] += seats;
        if (last < diff.size()) {
//            下车时在last座位清空，此时座位数为0
            diff[last] -= seats;
        }
    }
    
    vector<int> carDifferenceResult(vector<int> &diff) {
        vector<int> result(diff.size(), diff[0]);
        for (int i = 1; i < diff.size(); ++i) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
    
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        for (vector<int> &trip : trips) {
            carDifferenceIncrease(diff, trip[1], trip[2], trip[0]);
        }
        vector<int> result = carDifferenceResult(diff);
        for (int i = 0; i < 1001; ++i) {
            if (result[i] > capacity) {
                return false;
            }
        }
        return true;
    }
    
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int count = m * n;
        int leftBound = 0, upperBound = 0, rightBound = n - 1, bottomBound = m - 1;
        vector<int> res;
        res.reserve(count);
        while (res.size() < count) {
            if (upperBound <= bottomBound) {
                for (int i = leftBound; i <= rightBound; ++i) {
                    res.push_back(matrix[upperBound][i]);
                }
                ++upperBound;
            }
            if (leftBound <= rightBound) {
                for (int i = upperBound; i <= bottomBound; ++i) {
                    res.push_back(matrix[i][rightBound]);
                }
                --rightBound;
            }
            if (upperBound <= bottomBound) {
                for (int i = rightBound; i >= leftBound; --i) {
                    res.push_back(matrix[bottomBound][i]);
                }
                --bottomBound;
            }
            if (leftBound <= rightBound) {
                for (int i = bottomBound; i >= upperBound; --i) {
                    res.push_back(matrix[i][leftBound]);
                }
                ++leftBound;
            }
        }
        return res;
    }
    
};

class NumArray {
private:
    vector<int> preSums;
public:
    NumArray(vector<int>& nums) {
        int size = nums.size();
        preSums.resize(size + 1);
        preSums[0] = 0;
        for (int i = 1; i <= size; ++i) {
            preSums[i] = preSums[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) {
        return preSums[right + 1] - preSums[left];
    }
};


class NumMatrix {
private:
    vector<vector<int>> preSums;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        preSums = vector<vector<int>>(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                preSums[i][j] = preSums[i - 1][j] + preSums[i][j - 1] - preSums[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return preSums[row2 + 1][col2 + 1] - preSums[row1][col2 + 1] - preSums[row2 + 1][col1] + preSums[row1][col1];
    }
};
#endif /* arraySolution_hpp */
